For a device configured to guide a vehicle over a specified route, there is proposed a technique in which roads to travel are specified and then a route to travel is specified from lanes of each of the specified roads (see Japanese Patent Application Publication No. 2006-266865). This can improve accuracy of route guidance while reducing the processing load of lane-basis route searching.
However, the technique described in Japanese Patent Application Publication No. 2006-266865 has the following problem. The device selects each road to travel by using a link cost and traffic jam information. Accordingly, unless the device selects each road including a lane optimal as the route, the device cannot specify an optimal route, even though it specifies a travel route from lanes in the selected road. For example, a road in which only one of multiple lanes is congested is determined to be a congested road and is not selected as the road for specifying the travel route.